package com.markus.code.排序.base;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/4 20:33
 * todo:
 */
public class MergeSort {
    public static void mergeSort(int []arr){
        if (arr == null || arr.length == 0){
            return ;
        }
        sort(arr,0,arr.length-1);
    }
    private static void sort(int []arr,int start,int end){
        if (start >= end){
            return  ;
        }
        int mid = start + ((end-start)>>1);
//        System.out.println(mid);
        sort(arr,start,mid);
        sort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
    private static void merge(int []arr,int start,int mid,int end){
        int []temp = new int[arr.length];
        int index = start;
        int left = start;
        int right = mid+1;
        while(left <= mid && right <= end){
            if (arr[left] <= arr[right]){
                temp[index++] = arr[left++];
            }else{
                temp[index++] = arr[right++];
            }
        }
        while(left <= mid){
            temp[index++] = arr[left++];
        }
        while(right <= end){
            temp[index++] = arr[right++];
        }
        for (int i=start;i<=end;i++){
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int []arr = {3,6,4,7,1,8,1,5,5,9,6};
//        int []arr = {2,5,3,6,4};
        mergeSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
